package Demo;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class Lru {

    public static void main(String[] args) {
        LRUCache2 lruCache = new LRUCache2(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.cache);
        lruCache.get(2);
        System.out.println(lruCache.cache);

//        lruCache.put(3, 3);
//        System.out.println(lruCache.cache);

    }

    static class LRUCache extends LinkedHashMap<Integer, Integer> {

        private int capacity;

        LRUCache(int capacity) {
            super(capacity, 0.75f, false);
            this.capacity = capacity;
        }

        int get(int key) {
            return super.getOrDefault(key, -1);
        }

        void put(int key, int value) {
            super.put(key, value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    }


    static class LRUCache2 {

        class Node {
            int key;
            int value;
            Node prev;
            Node next;

            public Node() {
            }

            public Node(int k, int v) {
                key = k;
                value = v;
            }
        }

        private Map<Integer, Node> cache = new HashMap<Integer, Node>();
        private int size;
        private int capacity;
        private Node head;
        private Node tail;

        LRUCache2(int capacity) {
            this.size = 0;
            this.capacity = capacity;
        }

        int get(int key) {
            Node node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 移动
            moveToHead(node);
            return node.value;
        }

        void put(int key, int value) {
            Node node = cache.get(key);
            if (node == null) {
                node = new Node(key, value);
                addToHead(node);
                cache.put(key, node);
            } else {
                node.value = value;
            }
        }


        private void removeToHead(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }


        private void moveToHead(Node node) {
            removeToHead(node);
            addToHead(node);
        }

        private void addToHead(Node node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

    }

}
